package algo;

import intf.IPLine;
import intf.IPoint;
import intf.impl.PLineImpl;
import intf.impl.PointImpl;

import java.util.*;

import ru.ts.common.misc.*;
public class ConvexHull
{
	static final double EPSILON = 0.000001;
	static final int MAXPOLY = 200;
	static final int TEST_COUNT = 10;
	static Pnt first_point = new Pnt();

	static class Pnt implements Comparable
	{
		/**
		 * @param d
		 * @param e
		 */
		public Pnt( double x, double y)
		{
			// TODO Auto-generated constructor stub
			this.x = x;
			this.y = y;
		}

		/**
		 * 
		 */
		public Pnt()
		{
			// TODO Auto-generated constructor stub
		}

		public double x, y;

		/*
		 * (non-Javadoc)
		 * 
		 * @see java.lang.Comparable#compareTo(java.lang.Object)
		 */
		@Override
		public int compareTo( Object o )
		{
			Pnt p2 = (Pnt) o;
			// TODO Auto-generated method stub
			if ( x < p2.x )
				return -1;
			if ( x > p2.x )
				return 1;

			if ( y < p2.y )
				return -1;
			if ( y > p2.y )
				return 1;

			return 0;
		}
	}

	static class Polygon<Point> extends ArrayList<Point>
	{

	}

	static double signed_triangle_area( Pnt a, Pnt b, Pnt c )
	{
		return ((a.x * b.y - a.y * b.x + a.y * c.x - a.x * c.y + b.x * c.y - c.x
		        * b.y) / 2.0);
	}

	static boolean cw( Pnt a, Pnt b, Pnt c )
	{
		return signed_triangle_area(a, b, c) < -EPSILON;
	}

	static boolean ccw( Pnt a, Pnt b, Pnt c )
	{
		return signed_triangle_area(a, b, c) > EPSILON;
	}

	static boolean collinear( Pnt a, Pnt b, Pnt c )
	{
		return Math.abs(signed_triangle_area(a, b, c)) <= EPSILON;
	}

	/**
	 * Linear distance (Euklidean one)
	 * @param a
	 * @param b
	 * @return
	 */
	static double distance( Pnt a, Pnt b )
	{
		int i;
		final double dx = a.x - b.x;
		final double dy = a.y - b.y;
		double d = dx * dx + dy * dy;
		return Math.sqrt(d);
	}

	/**
	 * Square distance
	 * @param a
	 * @param b
	 * @return
	 */
	static double distance2( Pnt a, Pnt b )
	{
		final double dx = a.x - b.x;
		final double dy = a.y - b.y;
		double d = dx * dx + dy * dy;
		return d;
	}

	static Pnt copy_point( Pnt p )
	{
		Pnt ret = new Pnt();
		ret.x = p.x;
		ret.y = p.y;
		return ret;
	}

	public static IPLine convex_hull( ArrayList<PointImpl> points )
	{
		// Point to Pnt
		List<Pnt> pntList = new ArrayList<Pnt>();
		for(IPoint p : points)
			pntList.add(new Pnt(p.X(), p.Y()));

		// Make convex hull
		Polygon<Pnt> pgn = convex_hull(pntList);
		
		// Polygon to IPLine
		PLineImpl pline = new PLineImpl(pgn.size());
		for(int i = 0; i < pgn.size(); i++ )
		{
			Pnt pnt = pgn.get(i);
			pline.append(pnt.x, pnt.y);
		}
		pline.setEnclosed(true);
		return pline;
	}
	
	static Polygon<Pnt> convex_hull( List<Pnt> in )
	{
		Polygon<Pnt> hull = new Polygon<Pnt>();
		int top;
		int n = in.size();

		if ( n <= 3 )
		{
			for ( int i = 0; i < n; i++ )
				hull.add( i, in.get( i ) );
			return hull;
		}

		n = sort_and_remove_duplicates(in);
		first_point = copy_point(in.get(0));

		Comparator cmp = new Comparator()
		{
			public int compare( Object a, Object b )
			{
				Pnt p1 = (Pnt) a;
				Pnt p2 = (Pnt) b;
				if ( collinear(first_point, p1, p2) )
				{
					if ( distance2(first_point, p1) <= distance2(first_point, p2) )
						return -1;
					else
						return 1;
				}

				if ( ccw(first_point, p1, p2) )
					return -1;
				else
					return 1;
			};
		};
		Collections.sort(in, cmp);

		hull.add(0, copy_point(first_point));
		hull.add(1, copy_point(in.get(1)));

		in.add(n, copy_point(first_point));

		top = 1;
		int i = 2;

		while (i <= n)
		{
			if ( !ccw(hull.get(top - 1), hull.get(top), in.get(i)) )
				top--;
			else
			{
				top++;
				hull.add(top, copy_point(in.get(i)));
				i++;
			}
		}
		// set new hill size
		hull.subList( top, n ).clear();
		return hull;
	}

	static int sort_and_remove_duplicates( List<Pnt> in )
	{
/*		Comparator<Pnt> cmp = new Comparator<Pnt>()
		{
			public int compare( Pnt p1, Pnt p2 )
			{
				if ( p1.x < p2.x )
					return -1;
				if ( p1.x > p2.x )
					return 1;

				if ( p1.y < p2.y )
					return -1;
				if ( p1.y > p2.y )
					return 1;

				return 0;
			}
		};
*/		Collections.sort(in/*, cmp*/);
		Colls.uniqueSorted(in);
		return in.size();
	}

	static public void print_polygon( ConvexHull.Polygon pg )
	{
		for ( int i = 0; i < pg.size(); i++ )
		{
			Pnt pnt = (Pnt) pg.get(i);
			System.out.printf("(%f,%f)\n", pnt.x, pnt.y);
		}
	}

	static public void print( List<Pnt> pg )
	{
		for ( int i = 0; i < pg.size(); i++ )
		{
			Pnt pnt = (Pnt) pg.get(i);
			System.out.printf("(%f,%f)\n", pnt.x, pnt.y);
		}
	}

	static public void main( String[] args )
	{

		// load some random values in the square [0..10] [0..10]
		ArrayList<Pnt> lst = new ArrayList<ConvexHull.Pnt>();
		Random rnd = new Random();
		for ( int i = 0; i < TEST_COUNT; i++ )
		{
			lst.add(new Pnt(rnd.nextDouble() * 10.0, rnd.nextDouble() * 10.0));
		}
		ru.ts.common.misc.Text.sout("+++ test CONVEX HULL +++");
		ru.ts.common.misc.Text.sout("+ print initial array");
		print( lst );
		Polygon hull = convex_hull(lst);
		ru.ts.common.misc.Text.sout("+ print convex array");
		print_polygon(hull);
	}
}